#include "myTree.h"
#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;


void TreeNode::printNode()
{
    cout << this->data;
}

TreeNode::TreeNode(char ch, TreeNode* left, TreeNode* right, NodeTag left_tag, NodeTag right_tag) {
    data = ch;
    leftChild = left;
    rightChild = right;
    lTag = left_tag;
    rTag = right_tag;
}

TreeNode::~TreeNode() {
    if (lTag == Link && leftChild) delete leftChild;
    if (rTag == Link && rightChild) delete rightChild;

    leftChild = nullptr;
    rightChild = nullptr;
}

MyTree::MyTree() {
    root = nullptr;
    isThread = false;
}

MyTree::MyTree(const char *ch) {
    int index = 0;
    isThread = false;
    root = Build(ch, index);
}

TreeNode* MyTree::Build(const char *ch, int &index) {
    char tmp = ch[index++];
    if(tmp == '\0' || tmp == '@') return nullptr;
    

    TreeNode *new_node = new TreeNode(tmp, nullptr, nullptr, Link, Link);
    new_node->leftChild = Build(ch, index);
    new_node->rightChild = Build(ch, index);

    return new_node;
}

MyTree::MyTree(const MyTree& T) {
    isThread = T.isThread;
    root = Copy(T.root);
}

TreeNode* MyTree::Copy(TreeNode *T) {
    if (!T) return nullptr;
    TreeNode *newNode = new TreeNode(T->data, nullptr, nullptr, T->lTag, T->rTag);

    newNode->leftChild = Copy(T->leftChild);
    newNode->rightChild = Copy(T->rightChild);

    return newNode;
}

MyTree::~MyTree() {
    delete root; root = nullptr;
    isThread = false;
}

void MyTree::Order(TreeNode *T,int index) {
    if (!T) return;
    if(index == 1) {
        T->printNode();
        Order(T->leftChild, index);
        Order(T->rightChild, index);
    } else if (index == 2) {
        Order(T->leftChild, index);
        T->printNode();
        Order(T->rightChild,index);
    } else {
        Order(T->leftChild, index);
        Order(T->rightChild, index);
        T->printNode();
    }
}

void MyTree::preOrderTraverse() {
    Order(root, 1);
}

void MyTree::inOrderTraverse() {
    if(!isThread) {
        Order(root, 2);
    } else {
        TreeNode* node = root;
        while (node && node->lTag == Link) node = node->leftChild;

        while (node) {
            node->printNode();
            if (node->rTag == Thread) node = node->rightChild;
            else {
                node = node->rightChild;
                while (node && node->lTag == Link) node = node->leftChild;
            }
        }
    }
}

void MyTree::postOrderTraverse() {
    Order(root, 3);
}

int MyTree::countLeaf() {
    int ans;
    TreeNode *tmp = root;
    ans = count_leaf(tmp);
    return ans;
}

int MyTree::count_leaf(TreeNode *tmp) {
    if(tmp == nullptr) return 0;
    if(tmp->leftChild == nullptr && tmp->rightChild == nullptr) {
        return 1;
    }
    return count_leaf(tmp->leftChild) + count_leaf(tmp->rightChild);
}

int MyTree::countHeight() {
    return count_height(root);
}

int MyTree::count_height(TreeNode *tmp) {
    if(tmp == nullptr) {
        return 0;
    } else {
        int m = count_height(tmp->leftChild);
        int n = count_height(tmp->rightChild);
        return m > n ? m + 1 : n + 1;
    }
    return -1;
}

bool MyTree::isThreadedTree() {
    return isThread;
}

bool MyTree::inOrderThreading() {
    inorder_threading(root);
    isThread = true;
    return true;
}

/*void MyTree::inorder_threading(TreeNode *tmp) {
    TreeNode *threading_head = new TreeNode(tmp->data, nullptr, nullptr, Link, Thread);
    TreeNode *pre = threading_head;
    threading_head -> rightChild = threading_head;
    if(!tmp) threading_head -> leftChild = threading_head;
    else {
        threading_head -> leftChild = tmp;
        Inthreading(tmp, pre);
        pre->rTag = Thread;
        pre->rightChild = threading_head;
        threading_head -> rightChild = pre;
    }
}*/
void MyTree::inorder_threading(TreeNode *tmp) {
    TreeNode *pre = nullptr;
    Inthreading(tmp, pre);
    if(pre) {
        pre->rTag = Thread;
        pre->rightChild = nullptr;
    }
}

void MyTree::Inthreading(TreeNode *tmp, TreeNode *&pre) {
    if(tmp != nullptr) {
        Inthreading(tmp -> leftChild, pre);
        if(tmp -> leftChild == nullptr) {
            tmp->lTag = Thread;
            tmp->leftChild = pre;
        }
        if(pre && pre -> rightChild == nullptr) {
            pre->rTag = Thread;
            pre->rightChild = tmp;
        }
        pre = tmp;

        Inthreading(tmp->rightChild, pre);
    }
}

TreeNode* MyTree::locate_not_threading(TreeNode *tmp, const char& ch) {
    if(tmp == nullptr) return nullptr;
    if(tmp->data == ch) {
        return tmp;
    }
    TreeNode *left = locate_not_threading(tmp->leftChild, ch);
    if(left != nullptr) {
        return left;
    }

    TreeNode *right = locate_not_threading(tmp->rightChild, ch);
    return right;
}

TreeNode* MyTree::locate_threading(TreeNode* tmp, const char& ch) {
    if(!tmp) return nullptr;

    TreeNode* node = tmp;
    while(node->lTag == Link) node = node->leftChild;
    while(node) {
        if(node->data == ch) return node;
        if(node->rTag == Thread) node = node->rightChild;
        else {
            node = node->rightChild;
            while(node && node->lTag == Link) node = node->leftChild;
        }
    }
    return nullptr;
}

TreeNode& MyTree::locateNode(const char &ch) {
    if(isThread == false) {
        TreeNode *ans = locate_not_threading(root, ch);
        return *ans;
    }
    TreeNode *ans = locate_threading(root, ch);
    return *ans;
}

TreeNode* MyTree::pre(const TreeNode *tmp) {
    if(tmp == nullptr) return nullptr;
    if(tmp->lTag == Thread) {
        return tmp->leftChild;
    }

    TreeNode *p = tmp->leftChild;
    while(p->rTag == Link) {
        p = p->rightChild;
    }
    return p;
}

TreeNode& MyTree::preNode(const TreeNode& tmp) {
    TreeNode *ans = pre(&tmp);
    return *ans;
}

TreeNode* MyTree::next(const TreeNode *tmp) {
    if(tmp == nullptr) return nullptr;
    if(tmp->rTag == Thread) {
        return tmp->rightChild;
    }

    TreeNode *p = tmp->rightChild;
    while(p && p->lTag == Link) {
        p = p->leftChild;
    }
    return p;
}

TreeNode& MyTree::nextNode(const TreeNode &tmp) {
    TreeNode *ans = next(&tmp);
    return *ans;
}


HuffmanTree::HuffmanTree(const int &length, const int arr[]) {
    t_length = length;
    HuffmanTree_nums.resize(2 * t_length - 1);
    for(int i = 0; i < length; i ++) {
        HuffmanTree_nums[i].weight = arr[i];
    }
    int total = 2 * t_length - 1;
    for(int i = 0; i < total; i ++) {
        HuffmanTree_nums[i].parent = -1;
        HuffmanTree_nums[i].leftChild = -1;
        HuffmanTree_nums[i].rightChild = -1;
    }
    for(int i = t_length; i < total; i ++) {
        int min1, min2;
        min1 = min2 = INT_MAX;
        int pos1(-1), pos2(-1);
        for(int j = 0; j < i; j ++) {
            if(HuffmanTree_nums[j].parent == -1) {
                if(HuffmanTree_nums[j].weight < min1) {
                    pos2 = pos1;
                    min2 = min1;

                    pos1 = j;
                    min1 = HuffmanTree_nums[j].weight;
                } else if(HuffmanTree_nums[j].weight < min2) {
                    pos2 = j;
                    min2 = HuffmanTree_nums[j].weight;
                }
            }
        }

        HuffmanTree_nums[i].leftChild = pos1;
        HuffmanTree_nums[i].rightChild = pos2;
        HuffmanTree_nums[i].weight = HuffmanTree_nums[pos1].weight + HuffmanTree_nums[pos2].weight;
        HuffmanTree_nums[pos1].parent = i;
        HuffmanTree_nums[pos2].parent = i;
    }
}

HuffmanTree::~HuffmanTree() {
    HuffmanTree_nums.clear();
    t_length = 0;
}


void HuffmanTree::printHuffmanCodes() {
    vector<pair<int,string>> codes;

    int total = 2 * t_length - 1;
    
    for (int i = 0; i < t_length; i++) {
        string code = "";
        int child = i;
        int parent = HuffmanTree_nums[i].parent;

        while (parent != -1) {
            if (HuffmanTree_nums[parent].leftChild == child)
                code = "0" + code;
            else
                code = "1" + code;
            
            child = parent;
            parent = HuffmanTree_nums[child].parent;
        }

        codes.push_back({HuffmanTree_nums[i].weight, code});
    }
    
    sort(codes.begin(), codes.end(), [](pair<int,string>& a, pair<int,string>& b){ return a.first > b.first; });

    for(int i = 0; i < t_length; i ++) {
        cout << codes[i].first << ": " << codes[i].second << endl;
    }
}